/*
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
*/
#include "Lzw.h"
/*
//该步已move至 .h file 中
//#define MAX_BITS    12
//#define TABLE_SIZE  4096
*/

////////////////////Windows
#if _WIN32 || _WIN64

/*
 位写入器_init */
void bit_writer_init(BitWriter *bw, FILE *fp)
{
	bw->fp = fp;
	bw->buffer = 0;
	bw->bit_count = 0;
}
/*
 位写入
 概述：该函数将给定的整数编码写入到比特流中。
参数：
bw：指向 BitWriter 结构体的指针，用于管理比特流的写入。
code：要写入的整数编码。
bits：要写入的比特数。
@ret：无返回值。函数直接将数据写入到 BitWriter 结构体中管理的文件流中 */
void write_bits(BitWriter *bw, int code, int bits)
{
	unsigned int mask = (1U << bits) - 1; //  创建一个掩码，用于提取 code 中的特定位数
	unsigned int ucode = (unsigned int)code & mask; //  将 code 与掩码进行按位与操作，提取出特定位数

	bw->buffer |= ucode << (32 - bw->bit_count - bits); //  将提取出的特定位数左移到缓冲区的适当位置
	bw->bit_count += bits;
	//8位一write，直到缓冲区满
	while (bw->bit_count >= 8)
	{
		fputc((bw->buffer >> 24) & 0xFF, bw->fp);
		bw->buffer <<= 8;
		bw->bit_count -= 8;
	}
}

/*
 compulsory_flush_retain_bit */
void flush_bits(BitWriter *bw)
{
	while (bw->bit_count > 0)
	{
		fputc((bw->buffer >> 24) & 0xFF, bw->fp);
		bw->buffer <<= 8;
		bw->bit_count = (bw->bit_count > 8) ? (bw->bit_count - 8) : 0;
	}
}

/*
位读取器_init */
void bit_reader_init(BitReader *br, FILE *fp)
{
	br->fp = fp;
	br->buffer = 0;
	br->bit_count = 0;
}
/*
位读取 
概述：该函数从给定的 BitReader 结构中读取指定数量的位，并返回读取的结果。
参数：
br：指向 BitReader 结构的指针，该结构包含了读取位流所需的状态信息。
bits：要读取的位数。
@ret：
成功时返回读取的位值。
如果在读取过程中遇到文件结束符（EOF），且没有读取到任何位，则返回 -1。
如果在读取过程中遇到文件结束符（EOF），但已读取到部分位，则返回 -2。*/
int read_bits(BitReader *br, int bits)
{
	unsigned int result = 0;
	int bits_needed = bits;

	while (bits_needed > 0) //  循环读取位，直到满足需要的位数
	{
		if (br->bit_count == 0) //  如果当前缓冲区没有剩余位，需要从文件中读取新的字节
		{
			int c = fgetc(br->fp);

			if (c == EOF)
				return (bits_needed == bits) ? -1 : -2;

			br->buffer = (unsigned int)c << 24; //  将读取的字节放入缓冲区，并左移24位，以便后续操作
			br->bit_count = 8;
		}

//		int take = (bits_needed < br->bit_count) ? bits_needed : br->bit_count;
		int take = auto_nmemb(bits_needed, br->bit_count); //  计算需要从缓冲区中取出的位数

		result = (result << take) | ((br->buffer >> (32 - take)) & ((1 << take) - 1));

		br->buffer <<= take;
		br->bit_count -= take;
		bits_needed -= take;

	}

	return (int)result;
}

/*
LZW_compress_kernel */
long lzw_compress(FILE *input, FILE *output)
{

	CompressDict *dict = (CompressDict*)calloc(TABLE_SIZE, sizeof(CompressDict));

	BitWriter bw;
	bit_writer_init(&bw, output);

	int next_code = 258;
	int current_bits = INIT_BITS;
	int max_code = 1 << current_bits;

	write_bits(&bw, CLEAR_CODE, current_bits);

	int prefix = fgetc(input); //  从输入文件中读取第一个字符作为前缀
	if (prefix == EOF)
	{
		free(dict),fprintf(stderr,"lzw_compress_failed :EOF \n");
		return -1;
	}

	int c; //  用于存储从文件中读取的字符
	while ((c = fgetc(input)) != EOF)
	{
		unsigned char uc = (unsigned char)c;
		int index = dict[prefix].next[uc]; //  查找当前前缀和字符组合在字典中的索引

		if (index) //  如果索引存在，即字典中已有该前缀和字符组合
			prefix = index;

		else //  如果索引不存在，即字典中没有该前缀和字符组合
		{
			write_bits(&bw, prefix, current_bits);

			if (next_code < TABLE_SIZE) //  如果字典中的下一个代码小于字典大小
			{
				dict[prefix].next[uc] = next_code++; //  将当前前缀和字符组合添加到字典中，并更新下一个代码

				//位长调整条件
				if (next_code > max_code && current_bits < MAX_BITS)
				{
					current_bits++;
					max_code = 1 << current_bits;
				}
			}
			else
			{
				// 字典重置逻辑
				write_bits(&bw, CLEAR_CODE, current_bits);

				memset(dict, 0, TABLE_SIZE * sizeof(CompressDict));
				next_code = 258;
				current_bits = INIT_BITS;
				max_code = 1 << current_bits;

				write_bits(&bw, uc, current_bits); // 写入当前字符
				prefix = uc;

				continue; //  跳过当前循环，继续处理下一个字符
			}
			prefix = uc; //  将当前字符编码赋值给前缀变量
		}
	}

	write_bits(&bw, prefix, current_bits);
	write_bits(&bw, END_CODE, current_bits);

	flush_bits(&bw); //  刷新位写入器，确保所有数据都被写入输出

	free(dict), fprintf(stdout,"lzw_compress_fin ");
	/*
	获取压缩后数据大小 */ //准备增加压缩与否的判断原理。maybe,【没有的话就是时间不够没写，老师见谅】
	long pos = ftell(output);
	return (pos != -1) ? pos : 0;
}
/*
 LZW_decompress_kernel */
void lzw_decompress(FILE *input, FILE *output)
{
	DecompressDict *dict = (DecompressDict*)malloc(TABLE_SIZE * sizeof(DecompressDict));

	BitReader br;
	bit_reader_init(&br, input);

	int current_bits = INIT_BITS;
	int max_code = 1 << current_bits;
	int next_code = 258;

	// 初始化基础字典
	for (int i = 0; i < 256; i++)
	{
		dict[i].prefix = -1;
		dict[i].c = (unsigned char)i;
	}

	unsigned char stack[TABLE_SIZE]; //  用于存储解压过程中产生的字符序列

	int code = read_bits(&br, current_bits);
	if (code != CLEAR_CODE)
	{
//		fprintf(stderr, "[错误] 文件头无效\n");
		free(dict),fprintf(stderr,"lzw_decompress_failed : invaild_header  \n");
		return;
	}

	code = read_bits(&br, current_bits);
	if (code == END_CODE)
	{
		free(dict),fprintf(stderr,"lzw_decompress_failed : END_CODE \n");
		return;
	}

	int old_code = code;
	fputc(dict[code].c, output);

	unsigned char first_char = dict[code].c;

	while (1)
	{
		code = read_bits(&br, current_bits);
		if (code == -1 || code == END_CODE)
			break;

		// 处理字典重置
		if (code == CLEAR_CODE)
		{
			next_code = 258;
			current_bits = INIT_BITS;
			max_code = 1 << current_bits;

			// 完全重建字典
			for (int i = 0; i < 256; i++)
			{
				dict[i].prefix = -1;
				dict[i].c = (unsigned char)i;
			}

			// 读取重置后的第一个编码
			code = read_bits(&br, current_bits);
			if (code == -1 || code == END_CODE)
				break;

			old_code = code;
			fputc(dict[code].c, output);
			first_char = dict[code].c;

			continue;
		}

		int current_code = code; //  当前编码值
		int stack_ptr = TABLE_SIZE; //  堆栈指针，初始化为表大小

		// 代码验证
		if (current_code >= next_code)
		{
			if (current_code != next_code)
			{
				fprintf(stderr, "[致命错误] 非法编码：%d (允许范围：0-%d)\n",
				        current_code, next_code-1);
				free(dict), fprintf(stderr,"lzw_decompress_failed : illegal_code \n");

				exit(EXIT_FAILURE);
			}

			stack[--stack_ptr] = first_char; //  将第一个字符压入堆栈
			current_code = old_code; //  更新当前编码值为旧编码值
		}

		// 展开字符串
		while (current_code != -1)
		{
			if (stack_ptr <= 1)
			{
				fprintf(stderr, "[错误] 堆栈溢出\n");
				free(dict), fprintf(stderr,"lzw_decompress_failed : overflow \n");

				exit(EXIT_FAILURE);
			}
			stack[--stack_ptr] = dict[current_code].c; //  将当前码对应的字符压入栈中，并减少栈指针
			current_code = dict[current_code].prefix; //  更新当前码为其前缀码
		}
		first_char = stack[stack_ptr]; // 获取首字符

		// 写入解码数据
		fwrite(&stack[stack_ptr], 1, TABLE_SIZE - stack_ptr, output);

		// update字典
		if (old_code != -1 && next_code < TABLE_SIZE)
		{
			dict[next_code].prefix = old_code;
			dict[next_code].c = first_char;
			next_code++;
			//变长编码机制
			if (next_code > max_code && current_bits < MAX_BITS) //  如果next_code超过了当前的最大码值且当前位数小于最大位数，则增加位数
				current_bits++, max_code = 1 << current_bits;
		}

		old_code = code; //  将当前解码的code赋值给old_code，以便下一次使用
	}

	free(dict),fprintf(stdout,"lzw_decompress_fin ");
}

////////////////////Windows

////////////////////LINUX
#else //LINUX
// LZW压缩
void lzw_compress(FILE *input, FILE *output)
{
	/*init 字典表框架:
		初始化单字符字典。
	*/
	/* TODO (dmsj#1#): 后期用指针format来定义dictionary
	                   ，解决dynastic不足问题。 */
	LZWEntry dictionary[TABLE_SIZE];
	//init 字典基础值
	int dict_size = 256;
	for (int i = 0; i < 256; i++)
	{
		dictionary[i].prefix = -1; // = EOF
		dictionary[i].next = i;
	}
	/*start to create ：
	 the dynastic dictionary for DIr_tree.
	*/
	int current_code = fgetc(input);
	if (EOF == current_code)
	{
		perror("ERROR_fgetc ");
		return;
	}
	//	int next_code;
	/*	while ((next_code = fgetc(input)) != EOF)
		这个写法太啰嗦了，换成死循环，
		内加嵌套条件执行break语句，更好。
	*/
	while (1)
	{
		int next_code = fgetc(input);
		/* End case:
			此时还有上一次循环遗漏下来的
			原next_code[现current_code]未输出,
			故，在break前，用‘,’连接执行一个putw来输出。
		*/
		if ( EOF == next_code)
		{
			putw(current_code, output);
			break;//end
		}

		//find 现有条目。
		int found = 0;
		for (int i = dict_size - 1; i >= 256; i--)
		{
			if (dictionary[i].prefix == current_code &&
			        dictionary[i].next == next_code)
			{
				current_code = i,found = 1;
				break;
			}
		}
		if (!found) //no find : this is a new group.
		{
			putw(current_code, output);
			if (dict_size < TABLE_SIZE)
			{
				dictionary[dict_size].prefix = current_code;
				dictionary[dict_size].next = next_code;
				dict_size++;
			}
			current_code = next_code; // to the next
			/* TODO (dmsj#1#): 后期改成链表格式.
			*/
		}
	}
	//输出最后一个code,此步已经移至while 内的END_case中。
	//	putw(current_code, output);
}
// LZW解压
void lzw_decompress(FILE *input, FILE *output)
{
	/*init 字典表框架:
		初始化单字符字典。
	*/
	/* TODO (dmsj#1#): 后期用指针format来定义dictionary
	               ，解决dynastic不足问题。 */
	LZWEntry dictionary[TABLE_SIZE];
	//init 字典基础值
	int dict_size = 256;
	for (int i = 0; i < 256; i++)
	{
		dictionary[i].prefix = -1;
		dictionary[i].next = i;
	}
	//compress format is int,so use getw
	// 读取第一个编码
	int old_code = getw(input);
	if ( EOF == old_code)
	{
		perror("ERROR_getw ");
		return;
	}

	// 输出首个字符
	int current_char = dictionary[old_code].next;
	fputc(current_char, output);
//	int code;
//	while ((code = getw(input)) != EOF)
	int out_buffer[TABLE_SIZE];
	int buffer_index;
	while (1)
	{
		int new_code = getw(input);
		if (EOF == new_code)
			break;//end

		int code = new_code;
		// 反向填充
		buffer_index = TABLE_SIZE - 1;

		// 处理特殊case：code不在字典中
		if (code >= dict_size)
		{
			out_buffer[buffer_index--] = current_char;
			code = old_code;
		}

		// 回溯前缀链
		while (code >= 255)
		{
			out_buffer[buffer_index--] = dictionary[code].next;
			code = dictionary[code].prefix;
		}
		out_buffer[buffer_index--] = code;

		// 输出解码后的字符流
		current_char = code; // 记录第一个字符
		for (int i = buffer_index + 1; i < TABLE_SIZE; i++)
			fputc(out_buffer[i], output);

		// 添加到字典
		if (dict_size < TABLE_SIZE)
		{
			dictionary[dict_size].prefix = old_code;
			dictionary[dict_size].next = current_char;
			dict_size++;
		}

		old_code = new_code;
	}

}

#endif 	//Different case in Linux & Windows .